

class Node:
    def __init__(self, val, parent):
        self.parent = parent
        self.left = None
        self.right = None
        self.value = val

class Tree:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self, val):
        if self.root is None:
            self.root = Node(val, None)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if node.left is not None:
            if node.right is not None:
                self._add(val, node.right)
            else:
                node.right = Node(val, node)
        else: node.left = Node(val, node)

    def find(self, val):
        if self.root is not None:
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if val == node.value:
            return node
        elif (val < node.value and node.left is not None):
            return self._find(val, node.left)
        elif (val > node.value and node.right is not None):
            return self._find(val, node.right)

    def deleteTree(self):
        # garbage collector will do this for us. 
        self.root = None

    def printTree(self):
        if self.root is not None:
            self._printTree(self.root)

    def _printTree(self, node):
        if node is not None:
            self._printTree(node.left)
            print(str(node.v) + ' ')
            self._printTree(node.right)

    def get_all_nodes(self) -> list:
        node = self.root
        nodes = list()
        while True:
            if node is not None:
                nodes.append(node)
                if node.left is not None:
                    nodes.append(node.left)
                else: break
                if node.right is not None:
                    nodes.append(node.right)
                else: break
            node = node.right
        return nodes

